Ant Colony Optimization for TSP in Psyco Python

This is a continuation of Parallel Ant Colony Optimization for TSP in Standard ML, Multi-Core Ant Colony Optimization for TSP in Haskell, Multi-Core Ant Colony Optimization for TSP in Erlang, and Multi-Core Ant Colony Optimization for TSP in Scala. See first page for Ant Colony and TSP problem description. Here the program has been rewritten in the programming language Python.

Python is a dynamically typed language and is normally interpreted. It is object-oriented but has some functional features such as map, reduce, and lambda functions. All functions in Python are Parametrically Polymorphic (see my article Types and Programming Languages for details), which creates difficulties for efficient compilation.

Psyco is a compiler for Python. It is a just-in-time compiler, and uses the run-time type usage information to determine which functions should be native-compiled. It is a specializing compiler -- it will create multiple instantiations of the same function with different type parameters. It is very easy to use; just add 2 lines to the top of your program:

import psyco
psyco.full()
It is an experimental project. The documentation warns that map and lambda perform poorly, and that list comprehensions (often a reasonable substitute) should be used instead. The original developer has moved on to work on the PyPy project; I should investigate that later.

Compared to other tested languages the performance of uncompiled Python is average; with Psyco compilation it is surprisingly good.

See previous for details of test environment. Same test as before, but only a single core and 1/4 the work.

Versions

Python 2.5.2 (r252:60911, Jun 25 2008, 17:58:32) [GCC 4.3.1] on linux2 from Debian apt-get.

Psyco psyco-1.6-linux.i386-2.5 from SourceForge

Command Lines

time ./ant.py

Results

Erlang   Haskell   Scala   MLton_SML  Python Psyco
93       22        10      1.5        40     5.5
All times in seconds.

Code

Erlang
Haskell
MLton Standard ML
Scala
Python

Blog

Blog entry for comments here